package strings;

public class LongestSubStrng {
	
	//Longest common substring problem
	public static void main(String args[]) {
		
		System.out.println(longestSubString("artefakt", "frrteczka"));
		
	}

	private static String longestSubString(String s1, String s2) {
		
		if (s1 == null || s2 == null) {
			return null;
		}
		
		char []s1Tab = s1.toCharArray();
		char []s2Tab = s2.toCharArray();
		
		int[][] tab = new int[s1.length()][s2.length()+1];
		
		for (int i=0; i<s1.length(); i++) {
			for (int j=0; j<s2.length(); j++) {
				if (s1Tab[i] == s2Tab[j]) {
					tab[i][j] = getParentValue(tab, i-1, j-1) + 1;
					if (tab[i][j] > tab[i][s2.length()]) {
						tab[i][s2.length()] = tab[i][j];
					}
				} else {
					tab[i][j] = 0;
				}
			}
		}
		
		int max = -1;
		int row = -1;
		for (int i=0; i<s1.length(); i++) {
			if(tab[i][s2.length()] > max) {
				max = tab[i][s2.length()];
				row = i;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		int k = s2.length() - 1;
		while (k > 0 && tab[row][k] != max) {
			k--;
		}
		for (int i=0; i<max; i++) {
			sb.insert(0, s2Tab[k-i]);
		}
		
		return sb.toString();
	}

	private static int getParentValue(int[][] tab, int i, int j) {
		return (i >= 0 && j >= 0) ? tab[i][j] : 0;
	}

}
